//
//  1005. K次取反后的最大.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/21.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution1005 {
    // 要想和为最大。
    // 负数的最小值，进行一次反转
    // 正数的最小值，进行反转
    func largestSumAfterKNegations(_ nums: [Int], _ k: Int) -> Int {
        var nums = nums.sorted { first, second in
            return abs(first) > abs(second)
        }
        var idx = k
        // 将能反转的负数反转
        for i in 0..<nums.count {
            // 没有机会了
            if idx <= 0 {
                break
            }
            // 有效置反一个
            if nums[i] < 0 && idx > 0 {
                nums[i] = -nums[i]
                idx -= 1
            }
        }
        // 如果还有可以反转的机会，将绝对值最小的进行来回反转
        if idx >= 0 {
            let lastIndex = nums.count - 1
            nums[lastIndex] = idx % 2 == 1 ? -nums[lastIndex]: nums[lastIndex]
        }
        // 求和
        var sum = 0
        for item in nums {
            sum += item
        }
        return sum
    }
    
    static func test() {
        let nums = [2,-3,-1,5,-4], k = 2
        let result = Solution1005().largestSumAfterKNegations(nums, k)
        print(result)
    }
}
